\chapter{Kernel Structure}

The kernel will be composed by the following modules.

\section{PCB}
\label{pcb}

This module represents a Process Control Block (PCB) and offers functions to manipulate it.

The PCB is represented as a C struct defined with the following fields:
\begin{itemize}
	\item priority: integer that represents the process' priority. There are 42 priority levels in our system. In this OS, the smaller the priority level, the more important the process is.
	\item state: integer that represents the process' state. A state can be Waiting, Ready, Running or Delayed (represented by an associated integer).
	\item pid: integer that represents the process' identity.
	\item program: a reference to the program this process runs. It will be either the name of the program or a integer representing it.
	\item program\_counter: the value of Program Counter (PC) needs to be saved when context switch occurs. It will be saved using this 32-bits long field.
	\item registers: during a context switch, the registers are saved into the PCB. Here, we will use this field. The saved registers will be the 32 bits general purpose registers (except zero) and the Exception Program Counter register (in case the process is preempted while it is processing an interrupt). 
	\item messages\_queue: the queue where messages will be send to and receive from is located in the PCB. This queue is managed by its own module (see \ref{message_queue}).
	\item supervisors: each process can be supervised by some other processes. An array of pointers to the supervisors' PCBs is then kept in the supervised PCB to able able to know to which process termination must be signaled.
\end{itemize}

The module also provides functions to access and use PCBs, mainly getters and setters that will be defined like:
\begin{itemize}
	\item type get\_XXX(PCB* target): 

	returns the field XXX of the PCB pointed by target

	\item void set\_XXX(PCB* target, type newXXX):
	
	sets the field XXX of the PCB to the value newXXX. 
\end{itemize}

A pair of functions will then be defined for each field of the PCB.

\section{process\_management}
\label{process_management}

This module manages processes and their PCBs. It keeps track of all the active processes in the system using a table of PCBs.

It includes the following functions:
\begin{itemize}
	\item int create\_process(priority, program):

	 creates a new process by allocating a PCB to it. The parameters are the priority of the new process and the program it is to execute. Of course, the \textit{program} parameter will not be a copy of the code but only the address of the program's entry point. The function also allocates a stack to the new process by setting its sp register (not the actual sp register but the representation saved in the PCB) and puts its PCB in the scheduler's ready queue. The return value is an error code indicating whether the operation has been done sucessfully or not. 

	\item int remove\_process(pid):
	
	removes the process' PCB having \textit{pid} as pid from the table of the active processes and deallocate it. In a system with memory allocated at compile time, deallocate  means setting a flag indicating the PCB is no longer in use whereas in a system with dynamic memory allocation, it means freeing the memory. Thus, after a call to this function, the process \textit{pid} no longer exists in our system. The function returns an error code depending if the operation succeeded or failed. The scheduler is called at the end to avoid ending up with an idle system.

	\item int change\_priority(pid, new\_priority):

	sets the priority of the process having \textit{pid} as pid to \textit{new\_priority} and returns a code indicating if everything went well or not (for example, \textit{pid} does not reference a valid process). 

	\item PCB* get\_pcb\_by\_pid(pid):
	
	returns a pointer to the PCB of the process having \textit{pid} as pid or null if such a process does not exist.

	\item void place\_in\_ready\_queue(pid):

	places the PCB having \textit{pid} as pid in the ready and changes its state to ready. This function will be use to wake blocked or delayed processes up. %The scheduler is called after the process has been put back in the ready queue.

	\item void block(pid):

	sets the state of the PCB having \textit{pid} as pid to Waiting and removes it from the ready queue.% and calls the scheduler. 

	\item void delay(pid, duration):
	
	sets the state of the PCB having \textit{pid} as pid to Delayed and removes it from the ready queue. It also sets a timer that will fire an interrupt to wake the delay process up after \textit{duration} ms.
\end{itemize}

This modude depends on the PCB (section \ref{pcb}) module for the PCB definition and on the scheduler (section \ref{scheduler}) module for the access to the ready queue.

\section{scheduler}
\label{scheduler}

The scheduler has to schedule the processes according to our policy, that is priority scheduling with Round Robin (RR) to break ties. Since a process can arrive or terminate at any time, the timer generates an interrupt for each time quantum, even if there is no need to use RR at the moment. Thus, if a new process has arrived with the highest priority, it will be scheduled. That means this highest priority process might wait at most a time quantum in the ready queue before being scheduled.

 In order to achieve this, the scheduler uses the following data structures and global variables:
\begin{itemize}
	\item ready\_queue: it is an array (or a list with dynamic memory allocation) that contains the PCBs of processes ready to execute (so, their state field's value is Ready). To facilitate the scheduling task, this queue will be sorted by priority levels in such a way that high priority processes' PCBs will be on the top of the queue.
	\item in\_ready\_queue: it is an array as long as the number of priority levels. It counts the number of processes in the ready queue for each priority level. This information is then used by the scheduler to determine whether RR has to be used or not.
	\item PCB* running: it is a pointer to the PCB of the current running process. 
	\item round\_robin: indicates whether the scheduler is in RR mode or not.
	\item round\_robin\_index: indicates the position of the running process in the ready when the scheduler is in RR mode.
\end{itemize}

The scheduler's main task is obviously to select the next process to run. It includes the following functions:
\begin{itemize}
	\item void insert(pcb):
	
	inserts the PCB \textit{pcb} in the ready queue, making sure to keep the queue ordered. It also updates the in\_ready\_queue array.

	\item void remove(pcb):

	removes the PCB \textit{pcb} from the ready queue and decrements the correct slot in the in\_ready\_queue array.

	\item PCB* get\_first():
	
	returns a pointer to the first PCB of the ready queue (or NULL if the queue if empty).

	\item PCB* get\_by\_index(index):
	
	returns a pointer to the PCB at the position \textit{index} in the ready queue (or NULL if the requested index is empty). 

	\item PCB* get\_running():

	returns a pointer to the PCB of the running process.

	\item PCB* choose\_next\_process():

	selects the next process to run from the ready queue and returns a pointer to its PCB (NULL if the ready queue happens to be empty or if the selected process is already running). This algorithm being non-trivial, it is explained using C code:
	\lstinputlisting[frame=single]{files/choose_next_process.c}	

	\item void schedule():

	selects the next process that is to be run and tells the dispatcher to allocate the CPU to it. This is the function that is called when the timer's interrupt occurs.

\end{itemize}

This module needs to be aware about the PCBs and has then to include the PCB module (section \ref{pcb}). Besides, it works with the dispatcher module (section \ref{dispatcher}).

\section{dispatcher}
\label{dispatcher}

This role of this module is to allocate the processor to the process selected by the scheduler.

It includes the following functions:
\begin{itemize}
	\item void save(PCB* pcb):

	saves the registers in the PCB \textit{pcb}. It also saves the value of the PC into the corresponding field.

	\item void load(PCB* pcb):
	
	loads the registers from the PCB \textit{pcb}, using the \textit{registers} field. The last thing it does is loading the PC from the corresponding field. The CPU then starts executing the newly loaded process. 

	\item void context\_switch(PCB* save, PCB* load):

	Do the context switch between \textit{save} and \textit{load}.
\end{itemize}

\section{I/O modules}

The I/O devices are mapped in memory. That means that they are accessed using MIPS instructions like any other memory place. When a request is issued to write in a memory location where a device is mapped, the device detects is and connects the data bus to its correct hardware register. So, when the programmer thinks he is writing in the memory, he is actually writing into some registers in the device. This mechanism is totally transparent to the programmer. Thus, we do not have to care about how to interact with the device's hardware in this project, just writing at the correct memory location is enough.

To achieve that, we considered two solutions: using assembly language or the volatile C keyword. 

The first solution requires to write assembly code which will read and write into some predefined location of the memory, where the devices are mapped. That means a lot of small routines and potentially a lot of bugs.

The second solution, which we are going to use, uses the C keyword volatile. If a variable is marked as volatile, any access to it will be translated by an access to the memory. We can therefore define a volatile pointer to the correct memory location and any access to this pointer will access the memory where the device is mapped. Then, we just have to define a C struct representing the layout of the memory. During this step, it is very important that each field of the struct has the right size, otherwise it will not work. To do that, we had to go through the documentation of all the device in order to figure out how to organize things. Now, we can use the pointer (pointing to memory location where the correct device is mapped) to this struct to write or read the fields. Since it is volatile, it will be translated into actual memory accesses and everything will work.

\subsection{UART}

The address of the UART or tty0 device as given by the memory map is 0x1800\_03F8. This is physical address but knowing that the physical addresses from 0x1000\_0000 are mapped in virtual memory at addresses starting at 0xA000\_0000, we can know that the virtual address of this device is 0xB800\_03F8.

The C struct used to represent the tty0 device is defined as follows:
\begin{itemize}
	\item data: 8-bits long, represents the registers mapped at offset 0x00, that is RBR and THR (read and write registers).
	\item ier: 8-bits long, represents the IER register at offset 0x01. It allows the programmer to enable or disable different kind of interrupts.
	\item union: two registers (offset 0x02) are mapped at the same offset but with different roles, so we use an union to make programming easier
	\begin{itemize}
		\item iir: 8-bits long, represents the IIR register which gives information about the interrupts. It is read-only.
		\item fcr: 8-bits long, controls the FIFO mode of the device where some bytes can be buffered to reduce the number of interrupts. It is write-only.
	\end{itemize}
	\item lcr: 8-bits long, represents the LCR register (offset 0x03) which controls the data (its length for example).
	\item mcr: 8-bits long, represents the MCR register (offset 0x04). It controls the physical interface of the device. 	
	\item lsr: 8-bits long, represents the LSR register (offset 0x05) which gives information about the data and the registers manipulating it.
	\item msr: 8-bits long, represents the MSR register (offset 0x06) and gives the current state of the physical control lines of the device.
	\item scr: 8-bits long, represents the scratch register (offset 0x07). It is a general purpose register without specific meaning. It is used as a temporary.
\end{itemize}

Each field will be an union with a 8-bits long variable representing the whole register and a struct using bit fields to allow easy access to each bit in the register (without having to use masking).

The module also has a FIFO queue where processes that requests the UART when it is being used are queued, waiting for their turn. Besides, the current process using the device is called the owner and a pointer to its PCB is stored in a variable with the same name.

It is possible to use this device through the following functions:
\begin{itemize}
	\item char get():

	returns a character from the Receiver Buffer Register. If there is no data to get (flag Data Ready not set), it waits until a character becomes available. It does not do busy waiting but uses the Received Data Available interrupt.
	The following code shows how the code that gets input from the user (like the C function fgets) will look like:
	\lstinputlisting[frame=single]{files/lire.c}	
	%\item int get\_str(buffer,length):
	
	%reads a character using get() and transfers it into \textit{buffer}. The operation is repeated using interrupts (with the Received Data Avalaible interrupt) when a new character is available. It stops when \textit{length} characters have been read or if the current character is '\\r'. The '\\0' character is added at the end of the string.

	%\item int get\_int():

	%uses get\_str() to get the input from the user and tries to translate it in an integer. It returns 0 if the input is not an integer.

	\item void print(char):
	
	prints the character \textit{char} by setting the Transmitter Holding Register (THR). It also sets the Transmitter Holding Register Empty interrupt and blocks the process until the output is done.
	The following code shows how the code that prints output of the program (like the C function printf) will look like:
	\lstinputlisting[frame=single]{files/ecrire.c}	

	\item void set\_word\_length(value):

	sets the LCR's register Word Length Select bits using \textit{value}.	

	%\item int print\_int(int):

	%prints the right-most digit of the integer \textit{int}. If the integer counts more than one digit, the operation is repeated using interrupts (with the Transmitter Holding Register Empty interrupt).

	%\item int print\_str(str):

	%prints the null terminated string \textit{str} character by character using print() and interrupts like print\_int.
\end{itemize}
\subsection{LCD}

The physical address of the malta0 device is 0x1F00\_0000 and therefore the virtual address is 0xBF00\_0000. However, the registers are placed at offset 0x400. So, our pointer will point to the address 0xBF00\_0400.

A C struct is also used here to access the device. We have defined it as follows:
\begin{itemize}
	\item ledbar: 8-bytes long. Only the first byte is used and controls which LED is on and which is off. The 7 other bytes are not used but must be present in the struct. Bit fields will be used here to access each bit (and so each LED) independently. 
	\item asciiword: 8-bytes long. Only the first 4 bytes are used and the value stored will be displayed in hexadecimal on the LCD
	\item asciipos: array of eight 8-bytes long elements. Each element represents a LED and only the first byte is used to contain data. It contains the character that is printed on the LCD. The position 0 corresponds to the left most LED.
\end{itemize}

Like the UART, the malta0 device can be requested by several processes at the same time. To handle this, a FIFO queue and a owner variable are used, just like with the UART.

This device can only display and cannot be used to input data. The module defines the following functions:
\begin{itemize}
	\item void print\_LCD(data):

	prints \textit{data} using the asciiword field (and setting all the LEDs on). \textit{data} must be a 32-bits long variable. 

	\item void print\_LCD\_position(position, data):

	prints the 8-bits long variable \textit{data} using the LED at the position \textit{position}. The function sets the request LED on.

	\item void get\_LCD(PCB* pcb):

	the process described by \textit{pcb} tries to become the owner of the LCD. If this is not possible, it blocks itself in the FIFO queue.

	\item void release\_LCD():
	
	sets the owner variable to an empty value and wakes up the first process of the FIFO queue (if any).
\end{itemize}

\subsection{display}

This module defines functions that provide an abstraction layer to the UART and LCD modules. It includes system calls like the functions print\_str() and read\_str() presented above. It also defines other useful system calls like read\_int(), print\_int()...

This module does not deal with the devices by itself but use the appropriate module to do that. 

\subsection{clock}

The physical address of the rtc0 device is 0x1800\_0070 and so its virtual address is 0xB800\_0070.

The rtc0 device is accessed using a C struct, defined as follows:% The first one is called system\_time, represents the system time and is defined as follows:
\begin{itemize}
	\item seconds: 8-bits long, represents the byte at offset 0x00.
	\item seconds\_alarm: 8-bits long, represents the byte at offset 0x01.
	%\item minutes: 8-bits long, represents the byte at offset 0x02.
	%\item minutes\_alarm: 8-bits long, represents the byte at offset 0x03.
	%\item hours: 8-bits long, represents the byte at offset 0x04
	%\item hours\_alarm: 8-bits long, represents the byte at offset 0x05.
	%\item day\_week: 8-bits long, represents the byte at offset 0x06.
	%\item day\_month: 8-bits long, represents the byte at offset 0x07.
	%\item month: 8-bits long, represents the byte at offset 0x08.
	%\item year: 8-bits long, represents the byte at offset 0x09.
\end{itemize}

%The second C struct represents the actual device and has the following fields:
%\begin{itemize}
%	\item system\_time time: according to the memory map, the first 10 bytes are occupied by the different parts of the time. Note that the definition of system\_time has been done in such a way that it respects the memory map.
%	\item registerA: 8-bits long, represents the register A at offset 0x0A. This register allows the user to turn the clock on and to control the frequency of periodic interrupts.
%	\item registerB: 8-bits long, represents the register B at offset 0x0B. This register allows the user to enable or disable different kind of interrupts.
%	\item registerC: 8-bits long, represents the register C at offset 0x0C. This register contains flags indicating whether an interrupt occured or not.
%	\item registerD: 8-bits long, represents the register D at offset 0x0D. This register is not used in our system because it contains only one information that does not make sense in a simulation.
%	\item ram: an array of 114 bytes. It represents the general purpose RAM offered by the device. 
%\end{itemize}

In our context, we only have the registers for the seconds mapped in memory.

The device is accessed through the following functions:
\begin{itemize}
	\item void initialize\_rtc():
	
	starts the real time clock.

	\item system\_time get\_time():

	returns the system time. 
\end{itemize}

\section{message}
\label{message}
A message represents the data passed from a process to another and some metadata on it.

This module defines the message type as a C struct with the following fields:
\begin{itemize}
	\item from: the pid of the sender
	\item to: the pid of the receiver
	\item priority: priority of the message, used to do filtering.
	\item data: data encapsulated in the message. It will be represented by a C union with a field for each type in C. Different messages will therefore be able to have different kind of data.
	\item data\_flag: indicates what kind of data is present in this message. 
\end{itemize}

Like the module PCB, the functions this module offers are getters and setters for the different fields of a message.

This module can be compiled on its own and does not need to include any other module.

\section{message\_queue}
\label{message_queue}

This module defines what a message queue is and offers functions to use it.

A message queue is a C struct with an array of message (or a linked list when dynamic memory management will be implemented) and an integer counting the number of element in the array. The messages in the queue are ordered by priority.

The module's functions are:
\begin{itemize}
	\item int insert(message\_queue* queue,message):
	
	inserts the message \textit{message} in \textit{queue} and wakes up the receiver if needed. This function keeps the queue ordered by priority. It returns a code indicating whether the operation was sucessful or not.

	\item message get\_first(queue):

	returns the first message of \textit{queue} and removes it from the queue. If the queue is empty, the process is blocked until a message is available.

	\item message get\_by\_priority(queue, priority):
	
	returns the first message in \textit{queue} having \textit{priority} as priority. This function also removes it from the queue. If no message of the correct priority is found, the process is blocked until a new message arrives.

	\item message get\_from(queue, from):
	
	returns the first message coming from the process with the pid \textit{from}. It also removes it from the queue. This function blocks the process if no corresponding message is found until a new one arrives.

	\item message get\_first\_timeout(queue, timeout, int* code):
	
	This function does the same thing as get\_first(), except that the process can only be blocked during \textit{timeout} ms. When the time is elapsed and no correct message has arrived, the function reports an error using the third parameter \textit{code}. 
\end{itemize}

Of course, all the get\_* functions have their equivalent with a timeout. It behaves as described for get\_first\_timeout().

\section{message\_passing}
\label{message_passing}

This module provides an abstraction layer to the message and message\_queue modules. It includes functions that perform message passing using the afore mentioned modules.
These functions are:
\begin{itemize}
	\item int send\_\textit{type}(to, data):

	builds a message using the parameters (and the information known by the process) and sends it by using the message\_queue's function insert. It returns a code indicating if an error occured or not. The word \textit{type} in the name of the function has to be replaced with the type of data. For example, a function sending messages containing an integer will be called send\_int.

	\item message receive\_*(\textit{adequate parameters}):

	a receive function is defined for each get\_* function and takes the same parameters (except the queue which is retrieved from the PCB of the running process). It does exactly what its corresponding get\_* function does. 
\end{itemize}

This module needs the message\_queue (section \ref{message_queue} and message (section \ref{message}) modules in order to work.

\section{process\_supervision}
\input{qPS}
\section{dynamic\_memory\_allocation}
\input{qDMM}

